August 8th, 2013 12:30 PM

PAC

28.6% enumeration

71.4% graph theory

10 Pages (budget 15 minutes each)

• 5-7 minutes for a single question (before moving on)

For enumeration focus on

• Basics
• Permutations
• combinations

• Find coefficients of power series

• Apply definition of generating functions

• Bijections

• Compositions

• Unambiguous expressions for strings

• Solving nonhomogeneous recurrences

For graph theory focus on

• Basics
• Degrees
• HSL
• …

• Isomorphism

• Walks, paths, cycles
• Eulerian stuff
• Induction proofs
• Cycle proofs
• Longest path proofs

• Trees
• MST

• Planarity
• Euler's Theorem
• HSLFF
• 
• 
• 
• Edge substitutions

• Colouring

• Matchings
• Algorithms
• Kӧnig's Theorem
• Hall's Theorem

Optional studies

• String recursion

• Proof of Hamilton cycle theorem

• TSP

• Stable marriage

Study Materials

• Assignments

• Tutorial problems

• Definitions

• Theorems

• Assignment 11

• Final exam S2012
•  This years final is harder!

OH

Today 2-4

Next Tue, Wed 10-5

 Good luck!